package leetcode.code0947;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Solution {

	int max = 10001;

	public int index(int i, int j) {
		return i * max + j;
	}

	public int removeStones(int[][] stones) {
		Set<Integer> set = new HashSet<>();
		Map<Integer, List<Integer>> rows = new HashMap<>();
		Map<Integer, List<Integer>> cols = new HashMap<>();
		for (int i = 0; i < stones.length; i++) {
			int[] cur = stones[i];
			int r = cur[0], c = cur[1];
			rows.computeIfAbsent(r, k -> new ArrayList<>()).add(c);
			cols.computeIfAbsent(c, k -> new ArrayList<>()).add(r);
		}
		int ans = 0;
		for (int i = 0; i < stones.length; i++) {
			int[] cur = stones[i];
			int r = cur[0], c = cur[1];
			int index = this.index(r, c);
			if (!set.contains(index)) {
				ans += this.find(rows, cols, r, c, set) - 1;
			}
		}
		return ans;
	}

	private int find(Map<Integer, List<Integer>> rows, Map<Integer, List<Integer>> cols, int r, int c,
			Set<Integer> set) {
		int index = this.index(r, c);
		if (set.contains(index)) {
			return 0;
		}
		int ans = 1;
		set.add(index);
		for (int nc : rows.get(r)) {
			ans += this.find(rows, cols, r, nc, set);
		}
		for (int nr : cols.get(c)) {
			ans += this.find(rows, cols, nr, c, set);
		}
		return ans;
	}

}
